鏈路狀態資訊不確定下QoS路由之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：18.117.107.90

姓名

蔡瑜方(Yu-Fang Tsai ) 查詢紙本館藏

畢業系所

資訊工程研究所

論文名稱

鏈路狀態資訊不確定下QoS路由之研究
(Study of QoS Routing with Uncertain Link State Information)

相關論文

★ 無線行動隨意網路上穩定品質服務路由機制之研究	★ 應用多重移動式代理人之網路管理系統
★ 應用移動式代理人之網路協同防衛系統	★ 以訊務觀察法改善光突發交換技術之路徑建立效能
★ 感測網路與競局理論應用於舒適性空調之研究	★ 以搜尋樹為基礎之無線感測網路繞徑演算法
★ 基於無線感測網路之行動裝置輕型定位系統	★ 多媒體導覽玩具車
★ 以Smart Floor為基礎之導覽玩具車	★ 行動社群網路服務管理系統－應用於發展遲緩兒家庭
★ 具位置感知之穿戴式行動廣告系統	★ 調適性車載廣播
★ 車載網路上具預警能力之車輛碰撞避免機制	★ 應用於無線車載網路上之合作式交通資訊傳播機制以改善車輛擁塞
★ 智慧都市中應用車載網路以改善壅塞之調適性虛擬交通號誌	★ 車載虛擬交通號誌環境下 Green Wave 之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

現今的網際網路上傳輸著各種不同應用的訊務，而大多數的訊務都被處以相同的待遇：best effort，也就是儘可能的傳送這些封包，並未考慮其服務品質（quality of service，簡稱QoS）之需求，因此品質服務路由（QoS routing）的觀念被提出來改善這樣的情況。QoS路由的觀念就是根據某種訊務所需的QoS需求，計算一條符合其需求的路徑，故一個QoS路由演算法在計算路徑時非常依賴各鏈路之狀態資訊。隨著時間的推移，網路環境不斷改變將的不確定性鏈路狀態資訊（uncertain link state information）可能會使得QoS路由演算法做出錯誤的決策，如何在此不確定的鏈路狀態條件下做出適當的決策是很重要的課題。
本篇論文提出了一個名為最小變異路徑（Minimum Variant Path，簡稱MVP）的QoS路由演算法。不同於其他的演算法只著重於單一的鏈路成本，此演算法考量的是整體的路徑成本，其方法是找出一條鏈路品質與所需求之值差異量最小的路徑，如此能增加可用的鏈路數目，藉以計算出更多之路徑。另外此演算法還採用了一個稱為最小滿足比率（minimum satisfactory ratio）的概念來增進網路的整體效率。最小滿足比率的基本概念是某些訊務可允許某種程度上的品質服務損耗，因此此演算法可以根據一品質服務路由請求所指定的最小滿足比率來找出一條符合其需求的路徑。
以接受請求比率與接受頻寬比率的模擬結果顯示，在封包遺失率相似的情況之下，本篇論文所提出之最小變異路徑品質服務路由演算法的效能要比線性（Linear）品質服務路以及雙取線（Hyperbolic）由演算法平均分別高了5.58%與3.22%。

摘要(英)

Today’s Internet is about to carry various types of traffic generated from different applications. Most of them are treated as the same way, “best effort”, which forwards packets as possible without providing quality of services (QoS). The concept of QoS routing was proposed to provide guaranteed services done by finding a path satisfying the QoS requirements of the traffic. Thus a QoS routing algorithm heavily depends on the link state information, such as available bandwidth, delay, etc. For the network environment changes as time goes by, the link state information may no longer precious. Thus a QoS routing algorithm might make an inappropriate decision with uncertain link state information.
A QoS routing algorithm named Minimum Variant Path (MVP) is proposed in the thesis. The proposed algorithm focuses on the cost of the whole path instead of that of a single link. It tries to find a routing path that has the minimum mean variance between the available bandwidth of a link and the requested bandwidth specified in a QoS routing request. In the thesis, the traffic is assumed to be a certain degree of mission the QoS requirement, called satisfactory ratio. The proposed QoS routing algorithm is able to select a routing path to satisfy the QoS requirement with satisfactory ratio.
Simulation results show that without any increase in the packet loss rater, the proposed MVP QoS routing algorithm is capable of offering extra 5.58% and 3.22% requests in average than the Linear and Hyperbolic QoS routing algorithm, respectively.

關鍵字(中)

★ 不確定性鏈路狀態
★ 品質服務路由
★ 成本函數
★ 滿足比率

關鍵字(英)

★ cost function
★ QoS Routing
★ satisfactory ratio
★ uncertain link state

論文目次

Chapter 1 Introduction1
1.1 Background1
1.2 QoS Routing2
1.3 Goals7
1.4 Organization9
Chapter 2 Design of QoS Routing Algorithms10
2.1 Overview10
2.2 Updates Policy of Link State Information12
2.3 Uncertainty of Link State Information14
2.4 Definition of Link Cost Function16
2.5 Path Computation18
2.6 Path Selection Algorithm18
Chapter 3 The Proposed MVP QoS Routing Algorithm20
3.1 System Model20
3.1.1 Network Model20
3.2 Link State Prediction using Gaussian Function23
3.3 Minimum Variant Path Cost Function25
3.4 Proposed MVP QoS Routing Algorithm27
3.5 Performance Measures29
3.6 An Example30
Chapter 4 Simulations and Discussions35
4.1 Simulation Environment35
4.2 Simulation Results38
4.2.1 Effects of the Arrival Rate for QoS Routing Requests on the Performance39
4.2.2 Effects of the Packet Size on the Performance43
4.2.3 Effects of the Satisfactory Ratio on the Performance45
Chapter 5 Conclusions48

參考文獻

[1]E. Crawley, R. Nair, B. Rajagopalan and Hal Sandick, “A Framework for QoS-based Routing in the Internet,” INTERNET-RFC 2386, Internet Engineering Task Force, Aug. 1998.
[2]D. W. Shin, E. K. P. Chong and H. J. Siegel, “A Multiconstraint QoS Routing Scheme Using the Depth-First Search Method with Limited Crankbacks,” Proceedings of 2001 IEEE Workshop on High Performance Switching and Routing, Dallas, Texas, USA, pp. 29-31, May 2001.
[3]Z. S. Ma, Z. Peng and R. Kantola, “Influence of link state updating on the performance and cost of QoS routing in an intranet,” Proceedings of 2001 IEEE Workshop on High Performance Switching and Routing, Dallas, Texas, USA, pp. 375-379, May 2001.
[4]S. Zhang and Z. Liu, “A QoS Routing Algorithm based on Ant Algorithm,” Proceedings of 25th Annual IEEE Conference on Local Computer Networks, Tampa, Florida, USA, pp. 574-578, Nov. 2000.
[5]H. K. Pung, J. Song and L.Jacob, “Fast and Efficient Flooding based QoS Routing Algorithm, ” Proceedings of 8th International Conference on Computer Communications and Networks, Boston, Massachusetts, USA, pp. 298-303, Oct. 1999.
[6]S. Nelakuditi, R. P. Tsang and Z. L. Zhang, “Quality of Service Routing without Global Information Exchange,” Proceedings of 7th International Workshop on Quality of Service, UCL, London, UK, pp. 129-131, June 1999.
[7]D. H. Lorenz and A. Orda, “QoS Routing in Networks with Uncertain Parameters,” IEEE/ACM Transactions on Networking, vol. 6, no. 6, pp. 768-778, Dec. 1998.
[8]S. Chen and K. Nahrstedt, “Distributed QoS Routing with Imprecise State Information,” Proceedings of 7th International Conference on Computer Communications and Networks, Lafayette, LA, USA, pp. 614-621, Oct. 1998.
[9]Q. Ma and P. Steenkiste, “On Path Selection for Traffic with Bandwidth Guarantees,” Proceedings of IEEE International Conference on Network Protocols, Atlanta, Georgia, USA, pp. 191-202, Oct. 1997.
[10]A. Shaikh, J. Rexford and K. Shin, “Dynamics of Quality-of-Service Routing with Inaccurate Link-State Information,” University of Michigan Technical Report CSE-TR-350-97, Nov. 1997.
[11]G. Apostolopoulos, R. Guerin, S. Kamat and S. K. Tripathi, “Quality of Service based Routing: A Performance Perspective,” Proceedings of the ACM SIGCOMM '98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Vancouver, British Columbia, Canada, pp. 17-28, Sep. 1998.
[12]J. Wang, W. Wang, J. Chen and S. Chen, “A Randomized QoS Routing Algorithm On Networks with Inaccurate Link-State Information,” Proceedings of IEEE International Conference on Communication Technology, vol. 2, New Orleans, Louisiana, USA, pp. 1617-1622, Aug. 2000.
[13]A. Shaikh, J. Rexford, and K.G. Shin, “Evaluating the Impact of Stale Link State on Quality-of-Service Routing,” IEEE/ACM Transactions on Networking, vol. 9, no. 2, Apr. 2001.
[14]G. Apostolopoulos, R. Guerin, S. Kamat, A. Orda and S.K. Tripathi, “Intradomain QoS routing in IP networks: a Feasibility and Cost/Benefit Analysis,” IEEE Network, vol. 13, no. 5, pp. 42-54, Sep. 1999.
[15]A. Ariza, E. Casilari and F. Sandoval, “QoS Routing with Outdated Network Knowledge, ” Electronics Letters, vol. 32, no. 15, pp. 1332-1334, Jul. 2000
[16]G. Apostolopoulos, R. Guerin and S. Kamat, “Improving QoS Routing Performance Under Inaccurate Link State Information,” Proceedings of the 16th International Teletraffic Congress, Edinburgh, Scotland, UK, June 1999.
[17]R. Guerin and A. Orda, “QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms,” Proceedings of INFOCOM '97, vol. 1, Kobe, Japan, pp. 75-83, Apr. 1997.
[18]M. Barbehenn, “A Note on the Complexity of Dijkstra's Algorithm for Graphs with Weighted Vertices,” IEEE Transactions on Computers, vol. 47, no. 2, pp. 263,
[19]The Network Simulator — ns-2, http://www.isi.edu/nsnam/ns/
[20]D. Estrin, M. Handley, J. Heidemann, S. McCanne, X. Ya and H.Yu, “Network visualization with Nam, the VINT network animator,” Computer, vol. 33, no. 11, pp. 63-68, Nov. 2000.
[21]M. Ammar and U. Shankar, “On Path Selection for Traffic with Bandwidth Guarantees,” Proceedings of IEEE International Conference on Network Protocols, Atlanta, Georgia, USA, pp. 191-202, Oct. 1997.
[22]R. J. Sivasankar, S. Ramam, S.P. Subramaniam, T. Srinivasa Rao, D. Medhi, “Some Studies on the Impact of Dynamic Traffic in a QoS-based Dynamic Routing Environment,” Proceedings of IEEE International Conference on Communications, vol. 2, New Orleans, Louisiana, USA, pp. 959-963, June 2000.
[23]S. Chen and K. Nahrstedt, “An Overview of Quality of Service Routing for Next-Generation High-Speed Networks - Problems and Solutions,” IEEE Networks, vol. 12, no. 6, pp. 64-79, Nov. 1998.

指導教授

周立德(Li-Der Chou)

審核日期

2001-7-19

推文